/********************************************************************************
* @File name: mem_manage.c
* @Author: wzh
* @Version: 1.1
* @Date: 2021-8-14
* @Description: 内存管理算法，带有内存碎片合并算法，支持malloc、align_alloc、
*				realloc、free等常见的内存管理函数，支持多块内存合并管理，支持多线程
********************************************************************************/

#include "user_inc.h"

#define MEM_MANAGE_ALIGNMENT_BYTE_DEFAULT		8
#define MEM_MANAGE_BITS_PER_BYTE				8
#define MEM_MANAGE_MEM_STRUCT_SIZE				Mem_Manage_Align_Up(sizeof(Mem_Node),MEM_MANAGE_ALIGNMENT_BYTE_DEFAULT)
#define MEM_MANAGE_MINUM_MEM_SIZE				(MEM_MANAGE_MEM_STRUCT_SIZE<<1)
#define MEM_MANAGE_ALLOCA_LABAL					((size_t)(1<<(sizeof(size_t)*MEM_MANAGE_BITS_PER_BYTE-1)))


static inline size_t Mem_Manage_Align_Down(size_t data, size_t align_byte) {
	return data&~(align_byte - 1);
}

static inline size_t Mem_Manage_Align_Up(size_t data, size_t align_byte) {
	return (data + align_byte - 1)&~(align_byte - 1);
}

static inline Mem_Node* Mem_Manage_Addr_To_Mem(const void* addr) {
	return (Mem_Node*)((const uint8_t*)addr - MEM_MANAGE_MEM_STRUCT_SIZE);
}

static inline void* Mem_Manage_Mem_To_Addr(const Mem_Node* mem_node) {
	return (void*)((const uint8_t*)mem_node + MEM_MANAGE_MEM_STRUCT_SIZE);
}

//将内存节点插入空闲列表中
static inline void Mem_Insert_Node_To_FreeList(Mem_Root* pRoot, Mem_Node* pNode) {
	Mem_Node* pPriv_Node;
	Mem_Node* pNext_Node;
	//寻找地址与pNode相近的节点
	for (pPriv_Node = pRoot->pStart; pPriv_Node->next_node < pNode; pPriv_Node = pPriv_Node->next_node);
	pNext_Node = pPriv_Node->next_node;
	//尝试pNode与前一个块进行合并
	if ((uint8_t*)Mem_Manage_Mem_To_Addr(pPriv_Node) + pPriv_Node->mem_size == (uint8_t*)pNode) {
		if (pPriv_Node != pRoot->pStart) {//不是Start块的话可以合并
			pPriv_Node->mem_size += MEM_MANAGE_MEM_STRUCT_SIZE + pNode->mem_size;
			pNode = pPriv_Node;
		}
		else {//后面如果是Start块不进行合并，以免浪费内存
			pRoot->pStart->next_node = pNode;
		}
	}
	else {//不能合并时直接插入到空闲单链表中
		pPriv_Node->next_node = pNode;
	}
	//尝试后面一个块与pNode进行合并
	if ((uint8_t*)Mem_Manage_Mem_To_Addr(pNode) + pNode->mem_size == (uint8_t*)pNext_Node) {
		if (pNext_Node != pRoot->pEnd) {//不是end块的话可以进行块合并
			pNode->mem_size += MEM_MANAGE_MEM_STRUCT_SIZE + pNext_Node->mem_size;
			pNode->next_node = pNext_Node->next_node;
		}
		else {//后面如果是end块不进行合并，以免浪费内存
			pNode->next_node = pRoot->pEnd;
		}
	}
	else {//不能合并时直接插入到空闲单链表中
		pNode->next_node = pNext_Node;
	}
}

//获取管理内存的状态
void Mem_Manage_Get_State(Mem_Root* pRoot, Mem_State* pState) {
	MEM_MANAGE_ASSERT(pRoot->pStart != NULL);
	MEM_MANAGE_ASSERT(pRoot->pEnd != NULL);
	pState->max_node_size = pRoot->pStart->next_node->mem_size;
	pState->min_node_size = pRoot->pStart->next_node->mem_size;
	pState->remain_size = 0;
	pState->free_node_num = 0;
	MEM_MANAGE_LOCK();
	for (Mem_Node* pNode = pRoot->pStart->next_node; pNode->next_node != NULL; pNode = pNode->next_node) {
		pState->remain_size += pNode->mem_size;
		pState->free_node_num++;
		if (pNode->mem_size > pState->max_node_size)
			pState->max_node_size = pNode->mem_size;
		if (pNode->mem_size < pState->min_node_size)
			pState->min_node_size = pNode->mem_size;
	}
	MEM_MANAGE_UNLOCK();
}

//对齐分配内存
void* Mem_Manage_Align_Alloc(Mem_Root* pRoot, size_t align_size, size_t want_size) {
	void* pReturn = NULL;
	Mem_Node* pPriv_Node, *pNow_Node;

	MEM_MANAGE_ASSERT(pRoot->pStart != NULL);
	MEM_MANAGE_ASSERT(pRoot->pEnd != NULL);


	if (want_size == 0) {
		return NULL;
	}

	if ((want_size&MEM_MANAGE_ALLOCA_LABAL) != 0) {//内存过大
		MEM_MANAGE_MALLOC_FAIL();
		return NULL;
	}

	if (align_size&(align_size - 1)) {//内存对齐输入非法值
		MEM_MANAGE_MALLOC_FAIL();
		return NULL;
	}

	MEM_MANAGE_LOCK();
	if (want_size < MEM_MANAGE_MINUM_MEM_SIZE)
		want_size = MEM_MANAGE_MINUM_MEM_SIZE;
	if (align_size < MEM_MANAGE_ALIGNMENT_BYTE_DEFAULT)
		align_size = MEM_MANAGE_ALIGNMENT_BYTE_DEFAULT;
	//确保分配的单元都是MEM_MANAGE_ALIGNMENT_BYTE_DEFAULT的整数倍
	want_size = Mem_Manage_Align_Up(want_size, MEM_MANAGE_ALIGNMENT_BYTE_DEFAULT);

	pPriv_Node = pRoot->pStart;
	pNow_Node = pRoot->pStart->next_node;

	while (pNow_Node->next_node != NULL) {
		if (pNow_Node->mem_size >= want_size + MEM_MANAGE_MEM_STRUCT_SIZE) {
			size_t use_align_size;
			size_t new_size;
			pReturn = (void*)Mem_Manage_Align_Up((size_t)Mem_Manage_Mem_To_Addr(pNow_Node), align_size);//计算出对齐的地址
			use_align_size = (uint8_t*)pReturn - (uint8_t*)Mem_Manage_Mem_To_Addr(pNow_Node);//计算对齐所消耗的内存
			if (use_align_size != 0) {//内存不对齐
				if (use_align_size < MEM_MANAGE_MINUM_MEM_SIZE + MEM_MANAGE_MEM_STRUCT_SIZE) {//不对齐的值过小
					pReturn = (void*)Mem_Manage_Align_Up(\
						(size_t)Mem_Manage_Mem_To_Addr(pNow_Node) + MEM_MANAGE_MINUM_MEM_SIZE + MEM_MANAGE_MEM_STRUCT_SIZE, align_size);
					use_align_size = (uint8_t*)pReturn - (uint8_t*)Mem_Manage_Mem_To_Addr(pNow_Node);
				}
				if (use_align_size <= pNow_Node->mem_size) {
					new_size = pNow_Node->mem_size - use_align_size;//计算去除对齐消耗的内存剩下的内存大小
					if (new_size >= want_size) {//满足条件，可以进行分配
						Mem_Node* pNew_Node = Mem_Manage_Addr_To_Mem(pReturn);
						pNow_Node->mem_size -= new_size + MEM_MANAGE_MEM_STRUCT_SIZE;//分裂节点
						pNew_Node->mem_size = new_size;//新节点本来也不在空闲链表中，不用从空闲链表中排出
						pNew_Node->next_node = NULL;
						pNow_Node = pNew_Node;
						break;
					}
				}
			}
			else {//内存直接就是对齐的
				pPriv_Node->next_node = pNow_Node->next_node;//排出空闲链表
				pNow_Node->next_node = NULL;
				break;
			}
		}
		pPriv_Node = pNow_Node;
		pNow_Node = pNow_Node->next_node;
	}

	if (pNow_Node == pRoot->pEnd) {//分配失败
		MEM_MANAGE_UNLOCK();
		MEM_MANAGE_MALLOC_FAIL();
		return NULL;
	}

	if (pNow_Node->mem_size >= MEM_MANAGE_MINUM_MEM_SIZE + MEM_MANAGE_MEM_STRUCT_SIZE + want_size) {//节点内存还有富余
		Mem_Node* pNew_Node = (Mem_Node*)((uint8_t*)Mem_Manage_Mem_To_Addr(pNow_Node) + want_size);//计算将要移入空闲链表的节点地址
		pNew_Node->mem_size = pNow_Node->mem_size - want_size - MEM_MANAGE_MEM_STRUCT_SIZE;
		pNew_Node->next_node = NULL;
		pNow_Node->mem_size = want_size;
		Mem_Insert_Node_To_FreeList(pRoot, pNew_Node);
	}
	pNow_Node->mem_size |= MEM_MANAGE_ALLOCA_LABAL;//标记内存已分配
	MEM_MANAGE_UNLOCK();
	return pReturn;
}

void* Mem_Manage_Malloc(Mem_Root* pRoot, size_t want_size) {
	return Mem_Manage_Align_Alloc(pRoot, MEM_MANAGE_ALIGNMENT_BYTE_DEFAULT, want_size);
}

void* Mem_Manage_Realloc(Mem_Root* pRoot, void* src_addr, size_t want_size) {
	void* pReturn = NULL;
	Mem_Node* pNext_Node, *pPriv_Node;
	Mem_Node* pSrc_Node;
	MEM_MANAGE_ASSERT(pRoot->pStart != NULL);
	MEM_MANAGE_ASSERT(pRoot->pEnd != NULL);
	if (src_addr == NULL) {
		return Mem_Manage_Align_Alloc(pRoot, MEM_MANAGE_ALIGNMENT_BYTE_DEFAULT, want_size);
	}
	if (want_size == 0) {
		Mem_Manage_Free(pRoot, src_addr);
		return NULL;
	}

	MEM_MANAGE_LOCK();
	if ((want_size&MEM_MANAGE_ALLOCA_LABAL) != 0) {
		MEM_MANAGE_UNLOCK();
		MEM_MANAGE_MALLOC_FAIL();
		return NULL;
	}

	pSrc_Node = Mem_Manage_Addr_To_Mem(src_addr);

	if ((pSrc_Node->mem_size&MEM_MANAGE_ALLOCA_LABAL) == 0) {//源地址未被分配，调用错误
		MEM_MANAGE_UNLOCK();
		MEM_MANAGE_ASSERT((pSrc_Node->mem_size&MEM_MANAGE_ALLOCA_LABAL) != 0);
		MEM_MANAGE_MALLOC_FAIL();
		return NULL;
	}

	pSrc_Node->mem_size &= ~MEM_MANAGE_ALLOCA_LABAL;//清除分配标记
	if (pSrc_Node->mem_size >= want_size) {//块预留地址足够大
		pSrc_Node->mem_size |= MEM_MANAGE_ALLOCA_LABAL;//恢复分配标记
		pReturn = src_addr;
		MEM_MANAGE_UNLOCK();
		return pReturn;
	}
	//开始在空闲列表中寻找与本块相近的块
	for (pPriv_Node = pRoot->pStart; pPriv_Node->next_node <pSrc_Node; pPriv_Node = pPriv_Node->next_node);
	pNext_Node = pPriv_Node->next_node;

	if (pNext_Node != pRoot->pEnd && \
		((uint8_t*)src_addr + pSrc_Node->mem_size == (uint8_t*)pNext_Node) && \
		(pSrc_Node->mem_size + pNext_Node->mem_size + MEM_MANAGE_MEM_STRUCT_SIZE >= want_size)) {
		//满足下一节点非end，内存连续，内存剩余足够
		pReturn = src_addr;
		pPriv_Node->next_node = pNext_Node->next_node;//排出空闲列表
		pSrc_Node->mem_size += MEM_MANAGE_MEM_STRUCT_SIZE + pNext_Node->mem_size;
		want_size = Mem_Manage_Align_Up(want_size, MEM_MANAGE_ALIGNMENT_BYTE_DEFAULT);
		if (pSrc_Node->mem_size >= MEM_MANAGE_MINUM_MEM_SIZE + MEM_MANAGE_MEM_STRUCT_SIZE + want_size) {//去除分配的剩余空间足够开辟新块
			Mem_Node* pNew_Node = (Mem_Node*)((uint8_t*)Mem_Manage_Mem_To_Addr(pSrc_Node) + want_size);
			pNew_Node->next_node = NULL;
			pNew_Node->mem_size = pSrc_Node->mem_size - want_size - MEM_MANAGE_MEM_STRUCT_SIZE;
			pSrc_Node->mem_size = want_size;
			Mem_Insert_Node_To_FreeList(pRoot, pNew_Node);
		}
		pSrc_Node->mem_size |= MEM_MANAGE_ALLOCA_LABAL;//恢复分配标记
		MEM_MANAGE_UNLOCK();
	}
	else {
		MEM_MANAGE_UNLOCK();
		pReturn = Mem_Manage_Align_Alloc(pRoot, MEM_MANAGE_ALIGNMENT_BYTE_DEFAULT, want_size);
		if (pReturn == NULL) {
			pSrc_Node->mem_size |= MEM_MANAGE_ALLOCA_LABAL;//恢复分配标记
			MEM_MANAGE_MALLOC_FAIL();
			return NULL;
		}
		MEM_MANAGE_LOCK();
		memcpy(pReturn, src_addr, pSrc_Node->mem_size);
		pSrc_Node->mem_size |= MEM_MANAGE_ALLOCA_LABAL;//恢复分配标记
		MEM_MANAGE_UNLOCK();
		Mem_Manage_Free(pRoot, src_addr);
	}
	return pReturn;
}

//释放内存
void Mem_Manage_Free(Mem_Root* pRoot, void* addr) {
	Mem_Node* pFree_Node;
	MEM_MANAGE_ASSERT(pRoot->pStart != NULL);
	MEM_MANAGE_ASSERT(pRoot->pEnd != NULL);
	MEM_MANAGE_LOCK();
	if (addr == NULL) {
		MEM_MANAGE_UNLOCK();
		return;
	}
	pFree_Node = Mem_Manage_Addr_To_Mem(addr);

	if ((pFree_Node->mem_size&MEM_MANAGE_ALLOCA_LABAL) == 0) {//释放错误，没有标记
		MEM_MANAGE_UNLOCK();
		MEM_MANAGE_ASSERT((pFree_Node->mem_size&MEM_MANAGE_ALLOCA_LABAL) != 0);
		return;
	}

	if (pFree_Node->next_node != NULL) {//释放错误
		MEM_MANAGE_UNLOCK();
		MEM_MANAGE_ASSERT(pFree_Node->next_node == NULL);
		return;
	}
	pFree_Node->mem_size &= ~MEM_MANAGE_ALLOCA_LABAL;//清除分配标记
	Mem_Insert_Node_To_FreeList(pRoot, pFree_Node);//插入到空闲链表中
	MEM_MANAGE_UNLOCK();
}

void Mem_Manage_Heap_Init(Mem_Root* pRoot, const Mem_Region* pRegion) {
	Mem_Node* align_addr;
	size_t align_size;
	Mem_Node* pPriv_node = NULL;

	pRoot->total_size = 0;
	pRoot->pEnd = NULL;
	pRoot->pStart = NULL;

	for (; pRegion->addr != NULL; pRegion++) {
		align_addr = (Mem_Node*)Mem_Manage_Align_Up((size_t)pRegion->addr, MEM_MANAGE_ALIGNMENT_BYTE_DEFAULT);//计算内存块对齐后的地址
		if ((uint8_t*)align_addr > pRegion->mem_size + (uint8_t*)pRegion->addr)//对齐消耗的内存超过内存区
			continue;
		align_size = pRegion->mem_size - ((uint8_t*)align_addr - (uint8_t*)pRegion->addr);//计算对齐后剩下的内存大小
		if (align_size < MEM_MANAGE_MINUM_MEM_SIZE + MEM_MANAGE_MEM_STRUCT_SIZE)//对齐剩下的内存太小
			continue;
		align_size -= MEM_MANAGE_MEM_STRUCT_SIZE;//求除去掉表头后内存块的大小
		align_addr->mem_size = align_size;
		align_addr->next_node = NULL;
		if (pRoot->pStart == NULL) {//如果是初始化
			pRoot->pStart = align_addr;//将当前内存块地址记为start
			if (align_size >= MEM_MANAGE_MINUM_MEM_SIZE + MEM_MANAGE_MEM_STRUCT_SIZE) {//若剩下的块足够大
				align_size -= MEM_MANAGE_MEM_STRUCT_SIZE;//去掉下一个块的表头剩下的内存大小
				align_addr = (Mem_Node*)((uint8_t*)pRoot->pStart + MEM_MANAGE_MEM_STRUCT_SIZE);//下一个块的表头地址
				align_addr->mem_size = align_size;
				align_addr->next_node = NULL;
				pRoot->pStart->mem_size = 0;
				pRoot->pStart->next_node = align_addr;
				pRoot->total_size = align_addr->mem_size;
			}
			else {//内存太小了，将当前内存块地址记为start
				pRoot->total_size = 0;
				pRoot->pStart->mem_size = 0;
			}
		}
		else {
			pPriv_node->next_node = align_addr;//更新上一节点的next_node
			pRoot->total_size += align_size;
		}
		pPriv_node = align_addr;
	}
	//此时，pPriv_node为最后一个块，接下来在块尾放置表尾end
	//求出放置end块的地址,end块仅是方便遍历使用，因此尽量小，分配为MEM_MANAGE_MEM_STRUCT_SIZE
	align_addr = (Mem_Node*)Mem_Manage_Align_Down(\
		(size_t)Mem_Manage_Mem_To_Addr(pPriv_node) + pPriv_node->mem_size - MEM_MANAGE_MEM_STRUCT_SIZE, MEM_MANAGE_ALIGNMENT_BYTE_DEFAULT);
	align_size = (uint8_t*)align_addr - (uint8_t*)Mem_Manage_Mem_To_Addr(pPriv_node);//求出分配出end块后，前一个块剩余大小
	if (align_size >= MEM_MANAGE_MINUM_MEM_SIZE) {//若剩下的块足够大
		pRoot->total_size -= pPriv_node->mem_size - align_size;//去掉分配end块消耗的内存
		pRoot->pEnd = align_addr;			//更新表尾的地址
		pPriv_node->next_node = align_addr;
		pPriv_node->mem_size = align_size;
		align_addr->next_node = NULL;
		align_addr->mem_size = 0;//end块不参与内存分配，因此直接为0就可以
	}
	else {//最后一个块太小了，直接作为end块
		pRoot->pEnd = pPriv_node;
		pRoot->total_size -= pPriv_node->mem_size;
	}
	MEM_MANAGE_ASSERT(pRoot->pStart != NULL);
	MEM_MANAGE_ASSERT(pRoot->pEnd != NULL);
}




